Celtic

Trong phong cách di chuyển "một tấm vé mơ ước", Barnes được bổ nhiệm làm huấn luyện viên trưởng Celtic cho mùa 1999-2000, làm việc cùng Kenny Dalglish giữ vai trò là giám đốc điều hành. Sau đợt bổ nhiệm ông đính chính bản thân là một cầu thủ nhưng chưa bao giờ chơi một trận đấu mang tính cạnh tranh cho Celtic. Tuy nhiên cuộc hẹn mang đầy tính quảng cáo đã không thành công, bao gồm cú sốc thất bại Cúp Scotland dưới tay Inverness Caledonian Thistle vào tháng 2 (trong đó sinh ra tiêu đề nổi tiếng từ tờ The Sun: "Siêu Caley càng bắn đạn, Celtic càng trở nên tồi tệ"). Không lâu sau đó Barnes bị sa thải, còn Dalglish tiếp quản đội một cho đến cuối mùa giải.[25] Mặc dù Dalglish đoạt chức vô địch League Cup trong thời gian này, ông vẫn không được gia hạn hợp đồng và ban lãnh đạo quyết định thay thế ông bằng Martin O'Neill.

Jamaica

Barnes tiến đến những cuộc thảo luận với Liên đoàn bóng đá Jamaica vào tháng 2 năm 2008 về khả năng ông sẽ dẫn dắt đội tuyển bóng đá quốc gia nước này.[26] Ngày 16 tháng 9 năm 2008, Barnes được bổ nhiệm làm huấn luyện viên trưởng Jamaica trong khi Mike Commane làm trợ lý. Ông dẫn dắt nhiệm vụ Jamaica mới của mình tới vị trí thứ năm trong Caribbean Championships 2008, vượt qua vòng loại với vị trí dẫn đầu Caribbean tại Cúp vàng CONCACAF 2009.

Tranmere Rovers

Barnes chính thức trở thành huấn luyện viên trưởng Tranmere Rovers ngày 15 tháng 6 năm 2009 với Jason McAteer làm trợ lý cho ông.[27] Ông có một khởi đầu tồi tệ khi Tranmere chỉ thắng ba trong mười bốn trận đầu tiên của họ. Trong thời gian ở Tranmere bị gọi là "Dumb and Dumber" (Kẻ ngốc và ngốc hơn) bởi những cầu thủ Tranmere.[28] Ngày 9 tháng 10 năm 2009, Barnes bị câu lạc bộ sa thải sau thất bại muối mặt 5-0 tại Millwall và thành tích vỏn vẹn hai chiến thắng trong mười bảy trận tại giải đấu.[29] Từ đó ông chỉ làm huấn luyện viên trưởng của đội tuyển bóng đá quốc gia Rwandan cùng Stephen Garside làm huấn luyện viên đội trẻ.[30]